/**
 * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
 *
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 *
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
 *
 * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
 * 题解：https://labuladong.gitee.io/algo/4/31/111/
 */
class OpenLockBFS {
    /**
     * 法一：单向BFS
     * @param deadends
     * @param target
     * @return
     */
    public int openLock(String[] deadends, String target) {
        Deque<String> qu = new LinkedList<>();
        Set<String> visted = new HashSet<>();
        Set<String> deads = new HashSet<>();
        for(String deadend:deadends) {
            deads.add(deadend);
        }
        String start = "0000";
        qu.addLast(start);
        visted.add(start);
        int step = 0;
        while(!qu.isEmpty()) {
            int size = qu.size();
            for(int i=0;i<size;i++) {
                String cur = qu.pollFirst();
                if(deads.contains(cur)) {
                    continue;
                }
                if(cur.equals(target)) {
                    return step;
                }
                for(int j=0;j<4;j++) {
                    String up = plusOne(cur,j);
                    if(!visted.contains(up)) {
                        visted.add(up);
                        qu.addLast(up);
                    }
                    String down = minusOne(cur,j);
                    if(!visted.contains(down)) {
                        visted.add(down);
                        qu.addLast(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    private String plusOne(String cur,int j) {
        char[] cs = cur.toCharArray();
        if(cs[j]=='9') {
            cs[j]='0';
        } else {
            cs[j]+=1;
        }
        return new String(cs);
    }
    private String minusOne(String cur,int j) {
        char[] cs = cur.toCharArray();
        if(cs[j]=='0') {
            cs[j]='9';
        } else {
            cs[j]-=1;
        }
        return new String(cs);
    }

    /**
     * 法二：优化版，双向BFS
     */
    Set<String> deads = new HashSet<>();
    public int openLock(String[] deadends, String target) {
        Deque<String> qu1 = new LinkedList<>();
        Deque<String> qu2 = new LinkedList<>();
        Map<String,Integer> frontMap = new HashMap<>();
        Map<String,Integer> backMap = new HashMap<>();
        qu1.addLast("0000");
        qu2.addLast(target);
        frontMap.put("0000",0);
        backMap.put(target,0);
        for(String deadend:deadends) {
            deads.add(deadend);
        }
        while(!qu1.isEmpty()&&!qu2.isEmpty()) {
            int ret = -1;
            if(qu1.size()<= qu2.size()) {
                ret = update(qu1,frontMap,backMap);
            } else {
                ret = update(qu2,backMap,frontMap);
            }
            if(ret!=-1) {
                return ret;
            }
        }
        return -1;

    }
    private int update(Deque<String> qu,Map<String,Integer> map,Map<String,Integer> anthor) {
        int size = qu.size();
        for(int i=0;i<size;i++) {
            String cur = qu.pollFirst();
            if(deads.contains(cur)) {
                continue;
            }
            if(anthor.containsKey(cur)) {
                return map.get(cur)+anthor.get(cur);
            }
            int step = map.get(cur);
            for(int j=0;j<4;j++) {
                String up = plusOne(cur,j);
                if(!map.containsKey(up)) {
                    map.put(up,step+1);
                    qu.addLast(up);
                }
                String down = minusOne(cur,j);
                if(!map.containsKey(down)) {
                    map.put(down,step+1);
                    qu.addLast(down);
                }
            }
        }
        return -1;
    }
}